package leetcode.editor.cn;

import java.util.*;

class FindAllNumbersDisappearedInAnArray {
    public static void main(String[] args) {
        Solution solution = new FindAllNumbersDisappearedInAnArray().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public List<Integer> findDisappearedNumbers(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 1; i <= nums.length; i++) {
                map.put(i, 0);
            }

            for (int num : nums) {
                if (map.containsKey(num)) {
                    map.put(num, map.getOrDefault(num, 0) + 1);
                }
            }

            List<Integer> res = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 0) {
                    res.add(entry.getKey());
                }
            }

            return res;
        }*/

        // 进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
        // 原地修改
        public List<Integer> findDisappearedNumbers(int[] nums) {
            int n = nums.length;
            for (int num : nums) {
                int x = (num - 1) % n;   // 找到下标索引
                nums[x] += n;
            }

            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (nums[i] <= n) res.add(i + 1);
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
